package com.zp.self.module.level_4_算法练习.算法.广度优先搜索;



import com.zp.self.module.level_4_算法练习.数据结构.二叉树.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 二叉树的先序遍历  中、左、右
 * 二叉树的中序遍历  左、中、右
 * 二叉树的后序遍历  左、右、中
 * @author By ZengPeng
 * @Description
 * @date in  2020/9/29 15:34
 * @Modified By
 */
public class 二叉树3种遍历 {

    /**
     *  中续遍历:循环+队列
     * @param  root 树
     * @author  ZengPeng
     * @date  2020/10/9
     **/
    public List<Integer> middleTraverse(TreeNode root) {
        TreeNode p = root;//当前节点
        List<Integer>ans = new ArrayList<>();//结果顺序集合
        Deque<TreeNode> s = new ArrayDeque<>();//双端队列，感觉直接队列也行阿
        s.push(p);
        while(!s.isEmpty()) {
            p = s.poll();
            if(p.right==null && p.left==null)
                ans.add(p.val);
            else {
                if(p.right!=null)//不为null,压栈
                    s.push(p.right);

                s.push(new TreeNode(p.val));//当前节点

                if(p.left!=null)//不为null,压栈
                    s.push(p.left);
            }

        }
        return  ans;
    }

    /**
     *  先续遍历:循环+队列
     * @param  root 树
     * @author  ZengPeng
     * @date  2020/10/9
     **/
    public List<Integer> preorderTraverse(TreeNode root) {
        TreeNode p = root;//当前节点
        List<Integer>ans = new ArrayList<>();//结果顺序集合
        Deque<TreeNode> s = new ArrayDeque<>();//双端队列，感觉直接队列也行阿
        s.push(p);
        while(!s.isEmpty()) {
            p = s.poll();
            if(p.right!=null){//不为null,压栈
                s.push(p.right);
            }
            if(p.left!=null){//不为null,压栈
                s.push(p.left);
            }
            ans.add(p.val);
        }
        return  ans;
    }
    /**
     *  后续遍历:循环+队列
     * @param  root 树
     * @author  ZengPeng
     * @date  2020/10/9
     **/
    public List<Integer> postorderTraversal_good(TreeNode root) {
        TreeNode p = root;//当前节点
        TreeNode r = null;//上一个存储的值
        List<Integer>ans = new ArrayList<>();//结果顺序集合
        Deque<TreeNode> s = new ArrayDeque<>();//双端队列，感觉直接队列也行阿
        while(!s.isEmpty() || p != null) {
            if(p != null) {
                s.push(p);p = p.left;//先遍历最左端的
            } else {
                p = s.peek();//查栈
                if(p.right == null || p.right == r) {//判断右边 是否为空？ 或者右边的刚才已经存储（r）了
                    ans.add(p.val);//存储当前节点
                    r = p;//记录R
                    s.pop();//弹栈
                    p = null;
                } else
                    p = p.right;//右边树还没遍历呢....
            }
        }
        return  ans;
    }


}
